# This is a sample Python script.

# Press Shift+F10 to execute it or replace it with your code.
# Press Double Shift to search everywhere for classes, files, tool windows, actions, and settings.
from typing import List


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 最大和减去最小和就是 连续序列最大的值
        n = len(nums)
        maxSum = nums[0]
        minSum = sum0 = 0
        for i in range(n):
            # 求前n项和
            sum0 = sum0 + nums[i]
            # 求最大和
            maxSum = max(maxSum, sum0 - minSum)
            # 求最小和
            minSum = min(minSum, sum0)
        return maxSum

    # Press the green button in the gutter to run the script.


if __name__ == '__main__':
    nums = [5, 4, -1, 7, 8]
    solution = Solution()
    print(solution.maxSubArray(nums))

# See PyCharm help at https://www.jetbrains.com/help/pycharm/
